package HighMethod01;

//二分查找
public class StandardCopyTest04 {
    //非递归方式
    public static int BinaryFindValue(int []ar,int val)
    {
        if(ar == null || ar.length == 0) return -1;
        int left = 0, right = ar.length - 1;
        int pos = -1;
        while(left <= right) // while(left < right)
        {
            int mid = (left + right)/2; // mid = (right - left)/2 + left;
            if(val < ar[mid])
            {
                right = mid - 1;
            }else if(val > ar[mid]) {
                left = mid + 1;
            }else
            {
                //最左查找
                while(mid > left && ar[mid-1] == val) --mid;
                pos = mid;
                break;
            }
        }
        return pos;
    }

    //递归方式
    public static int SearchValue(int []ar,int left ,int right ,int val)
    {
        if(ar == null || ar.length == 0) return -1;

        int pos = -1;
        //***************
        if(left <= right &&right < ar.length)
        {
            int mid = (right - left)/2 + left;
            if(val < ar[mid])
            {
                pos = SearchValue(ar,left,mid-1,val);
            }else if(val > ar[mid])
            {
                pos = SearchValue(ar,mid+1,right,val);
            }else
            {
                //最右查找
                while(mid < right && ar[mid+1] == val) ++mid;
                pos = mid;
            }
        }
        return pos;
    }

    public static void main(String[] args) {
//                   0 1 2 3 4 5 6 7 8 9
        int arr[] = {1,2,2,3,4,7,7,7,8,9};
        int value = 0;
        System.out.println("非递归方式："+BinaryFindValue(arr,value));
        System.out.println("递归方式："+SearchValue(arr,0,arr.length,value));
    }

}
